package com.leetcode;
import java.util.Arrays;
import java.util.HashMap;

/**
 * @author LongYu
 * @date 2022/7/29 10:14
 */
public class D_75 {
    public static void main(String[] args) {
        int[] nums = {2,0,2,1,1,0};
//        int[] nums = {2,0,1};
        new D_75().sortColors2(nums);
        Arrays.stream(nums).forEach(System.out::println);
    }
    public void sortColors2(int[] nums) {
        if (nums.length == 0){
            return;
        }
        int pre = 0;
        int tail = nums.length -1;
        int i = 0;
        while (i <= tail){
            if (nums[i] == 1){
                i++;
            }else if (nums[i] == 0){
                int temp = nums[pre];
                nums[pre] = nums[i];
                nums[i] = temp;
                pre++;
                i++;
            }else if (nums[i] == 2) {
                int temp = nums[tail];
                nums[tail] = nums[i];
                nums[i] = temp;
                tail --;
            }
        }
    }





    /**
     * 暴力 算法 其实不用使用hashmap 直接int存 出现的次数
     * @param nums
     */
    public void sortColors(int[] nums) {
        HashMap<Integer, Integer> integerIntegerHashMap = new HashMap<>();
        for (int num : nums) {
            Integer integer = integerIntegerHashMap.get(num);
            if (integer != null) {
                integerIntegerHashMap.put(num, ++integer);
            } else {
                integerIntegerHashMap.put(num, 1);
            }
        }
        int integer =  integerIntegerHashMap.get(0) != null ? integerIntegerHashMap.get(0) : 0;
        int integer1 = integerIntegerHashMap.get(1) != null ? integerIntegerHashMap.get(1) : 0;
        int integer2 =  integerIntegerHashMap.get(2) != null ? integerIntegerHashMap.get(2) : 0;
        for (int i = 0; i < integer; i++) nums[i] = 0;
        for (int i = integer; i < integer + integer1; i++) nums[i] = 1;
        for (int i = integer + integer1; i < integer + integer1 + integer2; i++) nums[i] = 2;
    }
}
